package offer;

import java.util.Stack;

/**
 * @author ZhanBo
 * @date 2020/6/23
 */
public class Solution33 {

    public static void main(String[] args) {
        int [] array = {1,3,2,6,5};
        System.out.println(verifyPostorder(array));
    }

    /**
     * 剑指 Offer 33. 二叉搜索树的后序遍历序列
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
     * 参考以下这颗二叉搜索树：
     *       5
     *     / \
     *    2   6
     *   / \
     *  1   3
     *  输入: [1,6,3,2,5]
     * 输出: false
     * 输入: [1,3,2,6,5]
     * 输出: true
     * @param postorder
     * @return
     */
    public static boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(postorder[i] > root) {
                return false;
            }
            while(!stack.isEmpty() && stack.peek() > postorder[i]) {
                root = stack.pop();
            }
            stack.add(postorder[i]);
        }
        return true;
    }
}
